The invention can be applied in all fields where it is desirable to reduce the number of pieces of information necessary for the efficient representation of the digital image, in order to store it and/or transmit it. For example, the invention can be used for the transmission of images through the Internet. In this context, it enables the animation of 3D scenes with a real-time display, although the bit rate is neither constant nor guaranteed. In this case, the invention may be a primitive of a data transmission language such as VRML (or “Virtual Reality Modeling Language”).
Other applications that may be envisaged include the storage of animated data on CD-ROM (or any equivalent data carrier), multiple-user applications, digital television etc.
The invention proposes an improvement in methods known as “wavelet-based” methods through which a mesh can be represented as a succession of details added to a base mesh. The general theory of this technique is described especially in M. Lounsbery, T. DeRose and J. Warren, “Multiresolution Analysis for Surfaces of Arbitrary Topological Type” (ACM Transactions on Graphics, Vol. 16, No. 1, pp. 34-73).
According to this technique, a mesh is represented by a sequence of coefficients corresponding to the coordinates, in a wavelet base, of a parametrization of said mesh by a simple polyhedron.
A surface S in space can be represented as the image of an injective continuous function defined on a polyhedron Mo of the same topological type and having values in R3. It is then said that the surface is parametrized by the polyhedron, and the said function is called “parametrization”. This function is a triplet of functions with values in R, each of which can be developed in a base of the space Co(Mo) of the continuous functions on the polyhedron with values in R.
In the case of the mesh surfaces, this technique is used to obtain a compressed representation of the mesh. Furthermore, the use of wavelets as basic functions enables a progressive representation from the most approximate shape to the most detailed shape.
These functions are not wavelets in the classic sense, but comply with refining relationships that generalize the concept of multiresolution analysis: let Mo be a polyhedron on which a parametrization with a surfaceM is defined. We consider the sub-space So of Co(Mo) generated by the functions φio defined as follows: φi is affine on each facet; it is equal to 1 on the ith vertex and 0 on all the others.
A definition is made, in the same way, of the sub-spaces Sj generated by the functions φij defined in the same way but in replacing Mo by the mesh Mj obtained in canonically subdividing each facet of Mj−1. The spaces Sj are finite in dimension and nested, So being the smallest, and any continuous function of Mo in R can be approached uniformly by a function of a value of Sj for j as a fairly great value.
It is this inclusion that enables the progressive coding: if Wj denotes a supplementary of Sj in Sj+1 and {ψij}i (the wavelets) a base of Wj the set
            {              ϕ        i        o            }        i    ⋃            ⋃              j        ≥        o              ⁢                  {                  ψ          i          j                }            i      
forms a base of Co(Mo). The function p parametrizing M is therefore written uniquely as
where the values Ci and the values dij are in R3, and are called wavelet coefficients.
In practice, the wavelets are chosen in such a way that their support enables a determining of the wavelet coefficients in O(n), where n is the number of vertices of the mesh M: for k as a fixed integer, if Dk,i denotes the set of the indices of the vertices of a mesh Mj which are at a distance of less than k edges from the vertex i, the wavelet ψij is given by
            ψ      i      j        =                  ϕ        i                  j          +          1                    +                        ∑                      l            ∈                          D                              k                ,                i                                                    ⁢                              α            l                    ⁢                      ϕ            l            j                                ,
in such a way that ψij is with a support in Dk+1,i.
Thus, during the reconstruction, the influence of a wavelet coefficient is limited to a neighborhood of this kind.
In practice, during the reconstruction, the base mesh M0 is represented in arborescent form: each of its faces is the root of a tree where the children of each node are the four faces obtained after canonical subdivision. The wavelet coefficients are indexed by their barycentric coordinates on one face of M0.
The method of display comprising data structures and algorithms enabling the progressive reconstruction of meshes represented by wavelets has been proposed by A. Certain, J. Popovic, T. DeRose, D. Salesin and W. Stuetzle in “Interactive Multiresolution Surface Viewing”, (Computer Graphics Proceedings 1996).
This method is generally considered to be the method of reference in the field of the display of surfaces represented by wavelets.
This technique consists in taking account of packets of wavelet coefficients and in regularly refining the mesh as a function of these coefficients.
Although it is efficient for the progressive reconstruction of meshes, this method has the drawback of not enabling an adaptive display of three-dimensional scenes or objects.
Indeed, one drawback of this prior art technique is that it induces the creation, by subdivision, of unnecessary facets. This gives rise to an unnecessary increase in the number of pieces of data needed for the description of the mesh.
A technique of this kind is therefore far too cumbersome in terms of data to be transmitted to enable an adaptive display of 3D scenes or objects, especially when the objects are animated, when the power of the display terminal is low and/or when the transmission bit rate is variable and/or limited.
It is a goal of the invention especially to overcome these drawbacks of the prior art.
More specifically, it is a goal of the invention to implement a technique for the coding of meshes representing 3D objects and scenes, enabling an adaptive reconstruction of a mesh within a display terminal.
In particular, it is a goal of the invention to provide a coding method of this kind enabling an adaptive display of a 3D object or scene as a function of parameters, such as, for example, an observer's viewpoint.
It is another goal of the invention to provide a coding method of this kind enabling the user to navigate within a 3D scene refreshed at a substantially constant rate, independently of the parameters of the navigation or size of the associated mesh.
It is also a goal of the invention, naturally, to provide a technique for the reconstruction and transmission through a communications network of a coding object according to this coding method.